import java.util.HashMap;
import java.util.Map;

/**
 * 3. 无重复字符的最长子串
 */
public class Solution_3 {
    /**
     * 滑动窗口
     * 
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }

        // key 为字符，value 为该字符在字符串中的下标
        Map<Character, Integer> map = new HashMap<>();
        int ans = 0;
        // 双指针，子串从 left 开始，到 right 结束
        for (int left = 0, right = 0; right < len; right++) {
            char c = s.charAt(right);
            // 如果当前字符已经重复，则将窗口左边收窄
            if (map.containsKey(c)) {
                // 因为当前字符已出现重复，所以左边要从该字符上次出现的下一个位置开始
                left = Math.max(left, map.get(c) + 1);
            }
            // 更新当前字符在字符串中的下标
            map.put(c, right);
            // 更新无重复字符的最长子串的长度
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution_3 solution = new Solution_3();
        String s = "pwwwkew";
        int ans = solution.lengthOfLongestSubstring(s);
        System.out.println(ans);
    }
}
